2824. Road Removal

You are given a network with n cities and m bidirectional roads connecting these cities. The first k cities are important. You need to remove the minimum number of roads such that in the remaining network there are no cycles that contain important cities. A cycle is a sequence of at least three different cities such that each pair of neighboring cities are connected by a road and the first and the last city in the sequence are also connected by a road.

Input. The first line contains the number of test cases t (1 ≤ t ≤ 20).

Each case begins with a line containing integers n, m and k (1 ≤ n ≤ 10000, 1 ≤ m ≤ 50000, 1 ≤ k ≤ n), which represent the number of cities, the number of roads and the number of important cities, respectively. The cities are numbered from 0 to n – 1, and the important cities are numbered from 0 to k – 1. The following m lines contain two integers a_i and b_i, 0 ≤ i < m, that represent two different cities connected by a road.

It is guaranteed that 0 ≤ a_i, b_i < n and a_i ≠ b_i. There will be at most one road between two cities.

Output. For each of the test cases numbered in order from 1 to t, output "Case #i: " followed by a single integer, the minimum number of roads that need to be removed such that there are no cycles that contain an important city.

Sample input

2

5 7 2

0 1

1 2

1 4

0 2

2 4

2 3

3 4

8 12 2

0 2

0 4

0 5

2 3

2 7

3 1

3 4

4 6

5 6

5 7

6 1

7 1

Sample output

Case #1: 2

Case #2: 4

SOLUTION

система непересекающихся множеств

Анализ алгоритма

Очевидно, что ребра, не инцидентные важным городам, можно не удалять. Пусть подграф G’, состоящий из неважных вершин и ребер, не инцидентых важным городам, имеет c компонент связности. Рассмотрим граф, состоящий из k + c вершин:

· k вершин, пронумерованных от 0 до k – 1, и соответствующих важным городам;

· c вершин, пронумерованных от k до k + c – 1, соответствующих компонентам связности подграфа G’.

При этом из вершин, соответствующих компонентам связности G’, могут идти мультиребра в важные города.

Несмотря на то, что такой граф не обязательно является связным (это не гарантируется в условии задачи), запустим на нем алгоритм построения минимального остовного дерева, используя систему непересекающихся множеств. Считаем вес каждого ребра равным 1. Подсчитаем количество ребер в нем. Все ребра, не вошедшие в таким образом построенное остовное дерево, и которые являются инцидентными важным городам, следует удалить из исходного графа.

Пример

Рассмотрим первый пример, в котором города 0 и 1 являются важными. Можно удалить дороги (0, 1) и (1, 2), после чего оставшаяся сеть не будет содержать циклов, содержащих важные города.

Неважные вершины 2, 3, 4 с учетом ребер (3, 4), (2, 3), (2, 4) (не инцидентных важным вершинам), образуют одну компоненту связности. Стянем их во вторую вершину. Поскольку в исходном графе имеются ребра (1, 4) и (1, 2) то в новом появится мультиребро (1, 2). Для получения остовного дерева (графа без циклов) из результирующего графа следует удалить два ребра.

Рассмотрим еще один пример. Слева задан входной граф, справа – стянутый. Пусть k = 2. Неважные вершины с ребрами, не инцидентными важным вершинам, образуют две компоненты связности. Как видно из графа справа, для решения задачи достаточно удалить одно ребро.

Реализация алгоритма

Объявим структуру дороги (ребра) и массив дорог.

struct Edge

{

int u, v;

Edge(int a, int b) {u = a; v = b;}

};

vector<Edge> e;

Функция Repr возвращает представителя множества.

int Repr(int n)

{

if (n == mas[n]) return n;

return mas[n] = Repr(mas[n]);

}

Функция Union объединяет множества, содержащие элементы x и y. Возвращает 1, если x и y принадлежат одному множеству.

int Union(int x,int y)

{

int x1 = Repr(x),y1 = Repr(y);

mas[x1] = y1;

return (x1 == y1);

}

Основная часть программы. Последовательно обрабатываем входные тесты.

scanf("%d", &tests);

while(tests--)

{

scanf("%d %d %d", &n, &m, &k);

mas.resize(n, 0); e.clear();

Построим систему непересекающихся множеств из вершин графа.

for(i = 0; i < n; i++) mas[i] = i;

Неважные вершины, соединенные ребром, будем объединять в одно множество. В массив e занесем ребра, инцидентные важным городам.

for(i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

if ((a >= k) && (b >= k)) Union(a,b);

else e.push_back(Edge(a,b));

}

В переменной res подсчитаем количество ребер, инцидентных важным вершинам, и которые не попали в остовное дерево. Это значение и будет ответом задачи.

for(res = i = 0; i < e.size(); i++)

res += Union(e[i].u,e[i].v);

printf("Case #%d: %d\n",cs++,res);

}